The present invention relates to digital logic design, and, more specifically, to achieving an approximation of a clock gating function in digital logic by reducing the depth or number of paths of the function's corresponding binary decision diagram (“BDD”), thus yielding an approximated clock gating function with a smaller delay time.
Reducing power consumption in digital electronic logic circuits is currently one of the primary goals in digital logic design. Among the many techniques for power reduction, clock gating is well known, particularly for sequential or synchronous (i.e., “clocked”) circuits comprising combinational gates and storage components (e.g., edge-triggered flip-flops). Clock gating comprises the method of simply stopping the clock during certain periods of time; for example, when the flip-flops and/or its inputs are not changing state (i.e., the flip-flops are “idle”). Stopping the clock saves power because the energy dissipation of, e.g., a CMOS circuit, is directly related to the amount of switching activity occurring within the circuit.
The growing popularity of clock gating has given rise to the development of several tools for automatic clock gating in recent years. While many clock gating functions can be derived by a clock gating tool in a given design, some of the gating functions are not practical, for example, from a timing perspective. In such cases, these clock gating functions are most likely to be rejected by synthesis tools. In fact, timing constraints is one of the relatively more limiting factors for clock gating in high-performance electronic designs.
In an attempt to exploit the full potential of clock gating in a given design, methods for reducing the size of clock gating functions, commonly referred to as function approximation methods, have been suggested. An iterative method is known for approximating a function by reducing the number of function variables presented. At each iteration, the variable whose removal from the function results in the smallest error is eliminated by universal quantification. This method suffers from two primary disadvantages: first, it is relatively computationally demanding, as finding the best variable for elimination is performed by applying n universal quantifications, where n is the number of function variables. Secondly, it may result in too coarse of an approximation, thereby reducing the probability of the on-set too much, whereas a better clock gating condition, i.e., one with higher probability and thus one that saves more power that still satisfies timing constraints, can be derived. Another approach suggests an approximation heuristic that prunes minterms having probabilities below a given threshold, using a pseudo-Boolean function for representing minterm probabilities. A problem with this approach is that while it performs relatively finer approximation steps than in known methods, the minterm probabilities function can be exponentially large in the number of signals it depends on.
Besides the aforementioned analytical methods, a common practical approach represents the Boolean function of the clock gating function using a binary decision diagram (“BDD”) and approximates this function using the unique properties of such a representation. In general, a BDD is a directed acrylic graph (“DAG”) that is rooted and comprises a number of decision nodes and two terminal nodes referred to as the “0-terminal” and the “1-terminal”, with several paths passing through the decision nodes and ending at either one of the terminal nodes. The depth of a BDD is bounded from above by the number of variables of the BDD. Being a Boolean function in their nature, clock gating functions can be represented using BDDs. This type of representation allows the information relating to the clock gating function to be stored in a relatively compact manner, sometimes allowing the BDD representation to have a number of paths that is a polynomial in terms of the number of variables in the function. In general, the amount of time for evaluating the function represented by the BDD given a valuation of its variables is directly related to the depth or path length. Thus, a goal is to minimize the maximal path length of a BDD to reduce the corresponding amount of worst-time for evaluating the function.
Logic synthesis of BDDs (i.e., constructing a circuit which represents the Boolean function encoded by the BDD) may be carried out using known BDD decomposition techniques. As such, the logic depth and, thus, the logic delay of a digital logic electronic circuit obtained by BDD decomposition synthesis is correlated to the depth of the synthesized BDD. Therefore, from a timing perspective, it is desirable to represent Boolean functions with BDDs of relatively small depths or number of nodes. Although several methods exist for reducing the depth of a BDD by using a dynamic or static variable ordering algorithm, there are still cases where the BDD depth cannot be reduced below a desired threshold due, for example, to the complexity of the function logic.
Nevertheless, the usage of BDDs allows the use of alternative methods for function approximation. For example, an approximated function may be obtained by iteratively eliminating nodes in the BDD. BDD nodes that incur small approximation errors are eliminated by directing all incoming edges of these nodes to the zero-terminal node. However, since this method is applied independently on each level of the BDD, it reduces the BDD node count by decreasing the BDD width instead of its depth.
Unfortunately, none of the above known methods utilizes or considers timing constraints as approximation criteria during BDD reduction, but are directed instead at approximating functions while trading-off approximation error for BDD implementation size. No known method exists for approximating clock gating functions while considering timing constraints.